The development of intrusion technologies has brought great difficulties to intrusion detection. Traditional string matching based network intrusion detection systems, such as Snort (see document 1: Snort: Lightweight Intrusion Detection for Networks, M Roesch—LISA, 1999) can judge attacks merely on the basis of whether there is a certain signature in an single intercepted network data packet or whether certain ports are opened, but are unable to check the attacks veritably as a process, and therefore result in high false negative rate and false positive rate.
Depending on methods that can be used to detect attacks, Sandeep Kumar classified the attacks into categories of “existence”, “sequence”, and “partial order” (see document 2: S. Kumar and E. H. Spafford. A Pattern Matching Model for Misuse Intrusion Detection. In Proc. of the 17th National Computer Security Conference, 1994). “Existence” category refers to: once a certain event is found, it may be determined that an attack occurs. “Sequence” category refers to: it is determined that an attack occurs only when a series of events happen in a certain order, and detection for that category of attack requires storing variables for subsequent determination. “Partial order” category is wider than “sequence” category, and it doesn't requires a series of events happen in a certain order to identify an attack; a typical example is: when event A and event B happen before event C does, regardless of the order in which event A and event B happen, the events meet “partial order” relationship.
That puts forward requirements regarding methodology for designers of intrusion detection and prevention systems, that is, the detection model to be used must be capable of sufficiently and concisely expressing various attacks characterized by “existence”, “sequence”, and “partial order”, and, on that basis, efficiently identifying attacks.
To attain that goal, people have first tried to utilize variables to store states, and, based on that concept, adapted some procedural languages, for example, NFR's N-Code (see document 3: W. Lee, C. Park and S. Stolfo, Automated Intrusion Detection using NFR: Methods and Experiences, USENIX Intrusion Detection Workshop, 1999), SecureNet Pro's SNP-L, and open source software Bro developed by V. Paxson (see document 4: V. Paxson, Bro: A System for Detecting Network Intruders in Real-Time, USENIX Security Symposium, 1998), to perform state-based detection. In those systems, attack rules are written in procedural statement and variables are utilizes to store states, which requires a rule developer to have profound knowledge on the language execution mechanism. For a small system, it is not a problem; however, for a large-scale intrusion detection system in which protocol-level detection modules and attack rules have to be developed by several, several tens of, or even hundreds of programmers, it is quite difficult to require every programmer to have in-depth understanding on the internal execution mechanism of the detection language. That barrier results in poor expandability and maintainability of such systems.
To solve the above problem, people attempt to perform state-based intrusion detection with description languages, such as state transition language STATL (see document 5: S. T. Eckmann, G. Vigna, and R. A. Kemmerer. STATL: An Attack Language for State-based Intrusion Detection. In Proc. of ACM Workshop on Intrusion Detection, Athens, Greece, November 2000), Lambda (see document 6: F. Cuppens and R. Ortalo. LAMBDA: A Language to Model a Database for Detection of Attacks. In Proc. of RAID'00, LNCS vol. 1907, Springer, 2000), AdeLe (see document 7: C. Michel and L. M'e. ADeLe: an Attack Description Language for Knowledge-based Intrusion Detection. In Proc. of the 16th International Conference on Information Security, 2001), IDIOT developed by S. Kumar (see document 2), etc. However, the development in such languages requires defining explicitly “States” and “Transitions” in a reasoning process. This means that rule developers have to manually define an automaton for detection, which is too difficult for ordinary developers, however. Accordingly those languages are not genuine description languages.
Different from the above quasi-description languages, the Sutekh language developed by Pouzol (see document 8: Jean-Philippe Pouzol, Mireille Ducass é: From Declarative Signatures to Misuse IDS, RAID 2001) and the REE language developed by R. Sekar (see document 9: A High-Performance Network Intrusion Detection System, R Sekar, Y Guang, S Verma, T Shanbhag-ACM Conference on Computer and Communications Security, 1999) are genuine description languages. The two developers made valuable research in conversion of a state description rule to high-performance executable codes. However, both of the two languages are based on regular grammar and thereby have limited expression capability. In addition, due to the fact that the detection mechanism of regular grammar is finite automaton, the two languages have weak support for hierarchical processing capability required in protocol parsing.